package leetcode;

/**
 * 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 
 * 说明：每次只能向下或者向右移动一步。
 * 
 * @author maodou38
 *
 *
 *leetcode运行超时（无法执行）
 */
public class Solution64_mime {
	// 暴力考虑
	public int minPathSum(int[][] grid) {
		return calculate(grid, 0, 0);
	}

	/**
	 * 对每个坐标都考虑向右 向下
	 * 
	 * @param grid 矩阵数组
	 * @param i    横坐标
	 * @param j    纵坐标
	 * @return
	 */
	public int calculate(int[][] grid, int i, int j) {
		if (i == grid.length || j == grid[0].length) {
			// 超出矩阵边界
			return Integer.MAX_VALUE;
		}
		if (i == grid.length - 1 && j == grid[0].length - 1) {
			// 走到了终点
			return grid[i][j];
		}

		return grid[i][j] + Math.min(calculate(grid, i + 1, j), calculate(grid, i, j + 1));
	}
}
